package algorithm.sort;

import org.junit.Test;

/**
 * 二分插入排序
 *
 * @Author: zhenzhong.wang
 * @Time: 2018/4/9 11:18
 */
public class BinaryChopSort {

  @Test
  public void main() {
    int source[] = {10, 20, 6, 6, 7, 10, 3, 11};

    for (int i = 1; i < source.length; i++) {
      // 保留值
      int target = source[i];

      int low = 0, high = i - 1, middle;
      while (low <= high) {
        middle = (low + high) >>> 1;
        if (target < source[middle]) {
          high = middle - 1;
        } else {
          low = middle + 1;
        }
      }

      for (int j = i - 1; j >= low; j--) {
        source[j + 1] = source[j];
      }
      source[low] = target;
    }
    for (int a : source) {
      System.out.print(a + " ");
    }

  }


  @Test
  public void binarySort() {
    int source[] = {10, 20, 6, 6, 7, 10, 3, 11};
    int i, j;
    int high, low, mid;
    int temp;
    for (i = 1; i < source.length; i++) {
      // 查找区上界
      low = 0;
      // 查找区下界
      high = i - 1;
      //将当前待插入记录保存在临时变量中
      temp = source[i];
      while (low <= high) {
        // 找出中间值
        // mid = (low + high) / 2;
        mid = (low + high) >> 1;
        //如果待插入记录比中间记录小
        if (temp < source[mid]) {
          // 插入点在低半区
          high = mid - 1;
        } else {
          // 插入点在高半区
          low = mid + 1;
        }
      }
      //将前面所有大于当前待插入记录的记录后移
      for (j = i - 1; j >= low; j--) {
        source[j + 1] = source[j];
      }
      //将待插入记录回填到正确位置.
      source[low] = temp;
      System.out.print("第" + i + "趟排序：");
      printArray(source);
    }
  }

  public void printArray(int[] source) {
    for (int i = 0; i < source.length; i++) {
      System.out.print("\t" + source[i]);
    }
    System.out.println();
  }

}
